10143. Выбрасывание карт

Имеется колода из n карт, пронумерованных от 1 до n. Карта с номером 1 находится сверху, карта с номером n снизу. Следующая операция повторяется до тех пор, пока колода содержит не менее двух карт: верхняя карта выбрасывается, после чего находящаяся наверху карта кладется вниз колоды. Найдите последовательность выбрасываемых карт и номер карты, которая останется в конце.

Вход. Каждая строка содержит количество карт n (n ≤ 1000) в колоде. Последняя строка содержит n = 0 и не обрабатывается.

Выход. Для каждого теста вывести две строки. Первая строка должна содержать последовательность выбрасываемых карт, а вторая – номер оставшейся последней карты. Формат вывода показан ниже.

Пример входа	Пример выхода
7 10 6 0	Discarded cards: 1, 3, 5, 7, 4, 2 Remaining card: 6 Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8 Remaining card: 4 Discarded cards: 1, 3, 5, 2, 6 Remaining card: 4

РЕШЕНИЕ

очередь

Анализ алгоритма

По заданному числу n инициализируем колоду карт – двустороннюю очередь заполним числами 1, 2, …, n. Далее пока очередь содержит больше одного элемента совершаем n – 1 итерацию: выводим и удаляем верхнюю карту, после чего верхнюю карту кладем вниз колоды.

Пример

Промоделируем операции с колодой карт для n = 7.

Карта номер 6 останется в конце.

Реализация алгоритма

Объявим рабочую очередь.

deque<int> d;

Читаем входное значение n.

while (scanf("%d", &n), n)

{

Чистим очередь.

d.clear();

Инициализируем очередь (колоду карт) – заносим в нее последовательно числа от 1 до n.

for (i = 1; i <= n; i++) d.push_back(i);

printf("Discarded cards:");

for (i = 1; i < n; i++)

{

Выводим верхнюю карту и выбрасываем ее.

printf(" %d", d[0]); d.pop_front();

Верхнюю карту кладем вниз колоды.

d.push_back(d[0]); d.pop_front();

Между выводимыми картами следует вывести запятую.

if (i < n - 1) printf(",");

}

Выводим номер оставшейся карты.

printf("\nRemaining card: %d\n", d[0]);

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

LinkedList<Integer> q = new LinkedList<Integer>();

while(true)

{

int n = con.nextInt();

if (n == 0) break;

q.clear();

for (int i = 1; i <= n; i++)

q.addLast(i);

System.out.print("Discarded cards:");

for(int i = 1; i < n; i++)

{

System.out.print(" " + q.getFirst());

q.removeFirst();

q.addLast(q.getFirst());

q.removeFirst();

if (i < n-1) System.out.print(",");

}

System.out.println("\nRemaining card: " + q.getFirst());

}

con.close();

}

}

Python реализация

from collections import deque

while True:

n = int(input())

if n == 0: break

d = deque()

for i in range(n):

d.append(i + 1)

print("Discarded cards:",end = " ")

for i in range(n - 1):

print(d.popleft(),end = "")

d.append(d.popleft())

if i < n - 2: print(",",end = " ")

print("\nRemaining card:", d[0])